The present invention relates in general to a system and method for generating random numbers and, more particularly, to the generation of random numbers utilized in encrypting transmissions among and between computers and related devices in a network system.
An ever increasing number of individuals and companies use computer networks, such as the Internet, to transmit and process a wide variety of information. In some cases, the information transmitted is confidential or proprietary and there exists the potential for abuse if the information is accessed by an unauthorized third party. For example, increasing numbers of companies are exploring the option of taking orders for goods and services over the Internet. Similarly, there is increasing interest in conducting financial transactions, such as personal banking, over the Internet.
However, since ordering a product or service, or conducting personal banking over the Internet, may require the transmission of information such as a credit card number or a bank account number, there is an increasing need for heightened security to protect the information. The problem is further compounded by the inherent openness of a system such as the Internet that permits access to the vast volume of electronic messages which flow from user to user throughout the system. Normally, an individual user""s access is limited only to the extent that he or she has an account with a service provider, a valid password and account and/or mailbox identifiers. Passwords and identification numbers can, however, be acquired by third parties that, in turn, may disseminate the information to others. Further, in addition to data integrity and secrecy, authentication is an important factor. For example, bank account information should only be available to the owner of the account. Cryptographic authentication schemes and methods also make use of random numbers. Consequently, there is a growing need for reliable encryption of confidential and sensitive information.
To satisfy the need for transmission security, there have been a number of devices and algorithms developed for encoding information to be transmitted and decoding the information upon receipt. It is, of course, desirable to encrypt the information to be transmitted that makes it as difficult as possible to break the code or key used in the encryption process.
Typically, messages to be encrypted, referred to as plaintext, are encrypted using an encryption algorithm or cipher to produce ciphertext which is transmitted and subsequently decrypted by the receiver. In most cases the encryption algorithm is publicly known; in fact, by publicizing the algorithm, the cryptographer obtains the benefit of peer review by academic cryptologists attempting to break the cipher. Well known ciphers such as the Digital Encryption Standard (xe2x80x9cDESxe2x80x9d), the International Data Encryption Algorithm (xe2x80x9cIDEAxe2x80x9d) and RSA, known by the initials of the three discovers (Rivest, Shamir, Adleman), are widely used to encrypt electronic transmissions. Since most widely used ciphers are publicly known, it is a fundamental rule of cryptology that it must be assumed that the attacker knows the general method of encryption used to transform the plaintext to ciphertext. It must also be assumed that the attacker has the ability to intercept and accurately copy the ciphertext message.
The algorithms used for encrypting data tend to be complicated mathematical functions that require considerable effort and time to develop, test and implement. Consequently, it is impractical to invest the resources required to develop a new cipher each time the encryption method has been compromised or believed to be compromised. Thus, the secrecy of the encrypted message depends upon the key used to parameterize the algorithm. A key normally consists of a relatively short string of data that determines how an algorithm performs a specific encryption or decryption. In contrast to the general algorithm, which may be changed or modified only with the expenditure of significant resources, the key may be changed as often as required. One approach, known as public key cryptography, requires each user to have two keys: a public key used by the transmitting party to encrypt a message, and a private session key, used by the receiving party to decrypt the message. In many applications it is desirable to utilize a different, randomly chosen session key for each new connection. Session keys are used to minimize the amount of information protected by a selected key, thereby reducing the amount of information that an attacker could obtain by monitoring repeated transmissions and guessing any one session key. Session keys are also used to increase the speed of encryption.
The quality of the algorithm and the quality of the keys used by the algorithm are independent. If weak keys are selected, it does not follow that the algorithm is flawed or requires replacement. If, however, the encryption algorithm is weak, then the key selection does not ensure the security of the transmission. The converse is not true; i.e., if poor (no-random or partially random), keys are selected and the ciphertext is compromised, the breach is not a reflection upon the quality of the algorithm.
Usually, strong encryption methods require significant processing time due to the complexity of the algorithm. To increase the speed of encryption, a strong, secure algorithm such as RSA is initially used to negotiate a session key between two host computers. The session key is then used in a faster, but less secure, encryption algorithm such as DES to encrypt the communications between the two host machines. Since session keys change frequently and require the encryption of relatively little data, the risk presented by using a less secure algorithm is generally acceptable. However, the security of a cryptographic protocol utilizing a session key, or any other secret key, depends upon the unpredictability of the key. If an attacker can predict, or even reduce the number of possible keys that must be tested, the difficulty of breaking the key is greatly reduced; i.e. a predictable key is virtually worthless for the purpose of encrypting a transmission. Thus, random number generators are always used to generate session keys.
Random number generators are typically comprised of three components: 1) an internal state (value); 2) a randomizing function; and 3) an internal state update function. A binary bit stream consisting of zeros and ones may represent the internal state of the random number generator. Each time the random number generator is invoked, the randomizing function is performed on the internal state to produce a new random number and reinitialize the internal state using an internal state update function. The internal state provides input to the randomizing function, without which the random number generator would produce the same value repeatedly. The internal state update function allows the random number generator to create a sequence of random numbers by constantly changing the internal state with each iteration of the random number generator.
After the random number generator has been initialized or xe2x80x9cseededxe2x80x9d with an internal state it can generate one or more random numbers. However, due to the inherent deterministic nature of computers, the randomness of the output of the generator is dependent upon the randomness of the data or information utilized to initialize the generator. If the values used to initialize the generator are predictable, the output values from the generator will also be predictable. If the output of the random number generator is predictable, its value as a cryptographic tool is minimized. Therefore, the internal state update function will ideally minimize the occurrence of repeated internal states. However, if the internal state is repeated, the random numbers generated will be repeated.
Generating truly random numbers for use as keys for encrypting electronic messages presents a number of difficulties. The only measure of the true randomness of the output of normal random number generator is through the use of statistical analysis to determine the distribution, frequency and possible interdependence of the output. If these statistical criteria are not met, the output of the random number generator cannot be considered truly random. Additionally, providing random numbers for use as keys in encrypting electronic communications between computers presents further challenges. The randomizing function itself must be difficult to reverse or invert and the quantity of entropy in the random number stream must be sufficiently high to make guessing the internal state of the random number generator infeasible. The term xe2x80x9centropyxe2x80x9d as used herein refers to the concept of entropy in the context of information theory as discussed in C. E. Shannon, A Mathematical Theory of Communication, Bell Systems Technical Journal, v. 27, n. 4, 1948, pp. 379-423.
Entropy, in the cryptographic sense, is the amount of information that a message contains. In other words, cryptographic entropy can be viewed as the minimum number of bits required to represent the data of interest. Thus, the entropy of a random key is the number of bits required to represent all possible keys. Ideally, the entropy of a randomly selected key is equal to its length, i.e., every bit in the key is completely random and independent of every other bit in the key. Maximizing the amount of entropy contained in a cryptographic key is a primary consideration in encryption of electronic transmissions. The harder a particular key is to guess, the longer the encrypted data remains secret. The greater the amount of entropy contained in a key, the greater the difficulty in guessing the key or determining the key with a brute force attack.
The advent of high-speed processors has increased the difficultly of securely encrypting a transmission. The amount of processing power possessed by readily available present-day computers has made xe2x80x9cbrute forcexe2x80x9d attacks feasible. A brute force attack is one in which an exhaustive search of all possible keys is conducted. Current technology provides the means to test literally millions of possible keys in a matter of seconds. Therefore it is essential to maximize the amount of entropy utilized in the creation of an encryption key. If the entropy of the key is not equal to its size, the number of keys that would have to be tested in a brute force attack is reduced. For example, if the key is a six bit string or value, there are a total of 64 (2{circumflex over ( )}6) possible keys. However, if only even numbers are used in the key, the entropy of any one key is only five bits (2{circumflex over ( )}5=32) because the lowest order bit will always be equal to zero. Thus, the number of keys to test in a brute force attack upon the encryption is halved. Although the foregoing example is simplistic, it illustrates the need for entropy in random key generation.
Gathering entropy on a computer is a difficult task. Computers, by design, are deterministic predictable machines that execute a set of instructions in the exact same way each time the instructions are invoked. One possible solution to the problem of providing entropy is to install hardware in each computer that can generate random numbers based upon physical phenomena such as the rate of radioactive decay of an element or the thermal noise of a semiconductor diode. This solution is not viable due to a number of factors including cost and the perception that hardware sources of random numbers are not needed.
Many computer applications utilize external events to gather entropy such as the timing between a user""s keystrokes, movements of the mouse, or the input from a digitized audio source. However, in a network, where computers act as servers to other computers, as in the case of file servers, mail servers or web servers, these external sources of entropy do not exist. Server machines typically do not have any users that directly use the server from a monitor and keyboard; the user""s only interaction with the machine is over the network. Since these machines are isolated from random external physical phenomena, the task of acquiring entropy presents additional challenges. If a machine is required to generate a large number of cryptographic keys, for example as in the case of web server running Secure Sockets Layer (xe2x80x9cSSLxe2x80x9d), a cryptographic protocol developed to provide secure Internet transactions, the machine will have a high demand for entropy in the form of many generated session keys but no external source of random physical events. The same problem exists in the context of network firewalls and routers. These network devices rarely have any direct user interaction and typically communicate only with other computers.
Thus there exists a need for an improved method of providing the entropy necessary to generate random numbers used as secret keys for encrypting electronic communications between computers, and in particular, encrypting communications between computers on a network, such as the Internet.
The present invention provides a solution for the problems encountered in providing a quality source of entropy by sharing part of the internal state of each random number generator present on computers transmitting data over a network as the computers communicate. By sharing sources of entropy, session keys generated and utilized to encrypt the communications between computers are created from a larger pool of entropy. The method of the present invention improves the quality of entropy by allowing machines with no physical source of entropy to gather entropy by communicating with other machines and insuring that machines that generate many random session keys do not run the risk of depleting their local supplies of entropy. The present invention achieves these goals because, as the number of computers and systems communicating increases, the more entropy will be created.
The present invention provides a means of creating hard to guess secret keys needed for a variety of encryption algorithms and protocols. The invention allows network computers to generate and share entropy in proportion to the need to generate random numbers utilized to initialize an internal state or value that is subsequently processed by a random number generator to create secret session keys for communicating sensitive information over a computer network. In one embodiment, shared session keys are appended to the existing internal state of the random number generators residing on the communicating computers. The resulting bit stream is then mixed or xe2x80x9chashedxe2x80x9d using a one-way function such MD5 or SHA to produce a mixed bit stream. All or a portion of the mixed bit stream is then utilized as a source of entropy to reinitialize the internal state of the random number generator on one or both of the communicating computers.
The present invention provides features that have not previously been provided on a computer network. In particular, the invention supplies a steady stream of quality entropy to the random number generator; it satisfies the demand for more random session keys as the demand for keys increases; and it provides machines with poor or no sources of entropy, such as network servers, with an adequate source of quality entropy.
The present invention addresses the need for providing an unpredictable internal state (value) to a random number generator by distributing the state between multiple computing nodes. Although the amount of entropy provided by each node may be small, the cumulative entropy provided by all the nodes is large, thereby satisfying the need for a quality source of entropy.